class Solution {
    public boolean isValid(String s) {
        Deque<Character> stack = new LinkedList<>();
        for (char c : s.toCharArray()) {
            // 左括号入栈
            if (c == '[' || c == '(' || c == '{')
                stack.push(c);
            else {
                // 右括号且空栈，错
                if (stack.isEmpty()) return false;
                // 嵌套错误，错
                if ((c == ')' && stack.peek() != '(')
                    || (c == ']' && stack.peek() != '[')
                    || (c == '}' && stack.peek() != '{'))
                    return false;
                // 否则匹配成功，出栈
                stack.pop();
            }
        } 
        return stack.isEmpty();
    }
}